package leetcode.array;

/**
 * @Description: https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
 * @Author Ammar
 * @Create 2023/8/5 09:10
 */
public class _33_搜索旋转排序数组 {

    public static void main(String[] args) {
        new _33_搜索旋转排序数组().search(new int[]{3, 1}, 1);
    }

    public int search(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target) return 0;
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        return search(nums, target, left, right);
    }

    public int search(int[] nums, int target, int left, int right) {
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) return mid;
            if (nums[mid] >= nums[left]) {
                // 左边升序
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                    return search(nums, target, left, right);
                }
            } else if (nums[mid] <= nums[right]) {
                // 右边升序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                    return search(nums, target, left, right);
                }
            }
        }
        return nums[left] == target ? left : -1;
    }

    public int search1(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < nums[right]) {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
